package com.captjack.other;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jack Sparrow
 * @version 1.0.0
 * @date 2022/10/16 22:33
 * package com.captjack.other
 */
public class HanoiTower {

    public static void main(String[] args) {
        List<Integer> A = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            A.add(i);
        }
        List<Integer> B = new ArrayList<>();
        List<Integer> C = new ArrayList<>();
        hanota(A, B, C);
    }

    public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        /*
        递归求解:move(N,A,B,C)=move(n-1,A,C,B)+move(1,A,B,C)+move(n-1,B,A,C)
        1.先将的A柱子中的n-1个的圆盘移动到B柱子
        2.再将的A柱子中最后1个圆盘移动到C柱子
        3.最后将B柱子的n-1个圆盘移动到C柱子
         */
        int n = A.size();
        hanoiTowerMove(n, A, B, C);
        System.out.println(C);
    }

    public static void hanoiTowerMove(int n, List<Integer> a, List<Integer> b, List<Integer> c) {
        // n是a中圆盘数量
        if (n == 1) {
            // 将a中唯一一个移到c即可
            c.add(a.remove(a.size() - 1));
            System.out.println(a + "\t" + b + "\t" + c);
            return;
        }
        // 将上面n-1个圆盘由a移到b
        hanoiTowerMove(n - 1, a, c, b);
        // 将a中剩下的一个移到c
        c.add(a.remove(a.size() - 1));
        System.out.println(a + "\t" + b + "\t" + c);
        // 将b中的n-1个移动到c
        hanoiTowerMove(n - 1, b, a, c);
    }

}
